{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Алгоритмы и лямбды"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/algorithm\n",
    "\n",
    "https://en.cppreference.com/w/cpp/numeric\n",
    "\n",
    "https://en.cppreference.com/w/cpp/language/lambda"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Примеры и философия алгоритмов"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`accumulate` для знакомства"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "int sum_98(const std::vector<int>& v)\n",
    "{\n",
    "    int rv = 0;\n",
    "    for (std::vector<int>::const_iterator it = v.begin(), e = v.end(); it != e; ++it)\n",
    "        rv += *it;\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "int sum_range_for_11(const std::vector<int>& v)\n",
    "{\n",
    "    int rv = 0;\n",
    "    for (int x : v)\n",
    "        rv += x;\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "int sum_stl_accumulate(const std::vector<int>& v)\n",
    "{\n",
    "    // https://en.cppreference.com/w/cpp/algorithm/accumulate\n",
    "    return std::accumulate(v.begin(), v.end(), 0);\n",
    "    \n",
    "    // как это читать:\n",
    "    // std::accumulate(  // просуммировать элементы из последовательности (std::plus - дефолтная операция у accumulate)\n",
    "    //      v.begin(),   // итератор на первый элемент\n",
    "    //      v.end(),     // итератор на следующий за последним\n",
    "    //      0);          // начальное значение суммы\n",
    "}\n",
    "\n",
    "int sum_stl_reduce(const std::vector<int>& v)\n",
    "{\n",
    "    // https://en.cppreference.com/w/cpp/algorithm/reduce (C++17)\n",
    "    return std::reduce(v.begin(), v.end());\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Референсная реализация `std::accumulate` (см. документацию):\n",
    "\n",
    "```c++\n",
    "template<typename InputIt,\n",
    "         typename T,\n",
    "         typename BinaryOperation>\n",
    "T accumulate(InputIt first,\n",
    "             InputIt last,\n",
    "             T init, \n",
    "             BinaryOperation op)\n",
    "{\n",
    "    for (; first != last; ++first)\n",
    "        init = op(init, *first);\n",
    "\n",
    "    return init;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`count` - ещё пример"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "size_t count_range_for_11(const std::vector<int>& v, int val)\n",
    "{\n",
    "    size_t rv = 0;\n",
    "    for (auto x : v)\n",
    "        if (x == val)\n",
    "            ++rv;\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "size_t count_stl(const std::vector<int>& v, int val)\n",
    "{\n",
    "    return std::count(v.begin(), v.end(), val);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Референсная реализация `std::count`:\n",
    "\n",
    "```c++\n",
    "template<typename InputIt,\n",
    "         typename T>\n",
    "typename iterator_traits<InputIt>::difference_type\n",
    "count(InputIt first,\n",
    "      InputIt last,\n",
    "      const T& value)\n",
    "{\n",
    "    typename iterator_traits<InputIt>::difference_type ret = 0;\n",
    "    for (; first != last; ++first) {\n",
    "        if (*first == value)\n",
    "            ret++;\n",
    "    }\n",
    "    return ret;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`find`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "bool contains_range_for_11(const std::vector<int>& v, int val)\n",
    "{\n",
    "    for (int x : v)\n",
    "        if (x == val)\n",
    "            return true;\n",
    "    return false;\n",
    "}\n",
    "\n",
    "bool contains_stl(const std::vector<int>& v, int val)\n",
    "{\n",
    "    return std::find(v.begin(), v.end(), val) != v.end();\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "На примере `find` обсудить вопрос что лучше: наивная реализация или переиспользование алгоритма:\n",
    "* какой код чище?\n",
    "* вопрос уровня абстракции\n",
    "* оптимизации внутри алгоритмов\n",
    "* проблема читабельности алгоритмов:\n",
    "    * сколько служебных конструкций и повторений содержит элементарный код проверки, что `v` содержит `val`?\n",
    "    \n",
    "    ```c++\n",
    "    std::find(\n",
    "        current_students_in_the_class.begin(),\n",
    "        current_students_in_the_class.end(),\n",
    "        \"those little boy Einstein\")\n",
    "        != current_students_in_the_class.end();\n",
    "    ```\n",
    "    \n",
    "* ranges to the rescue! (но не совсем и с кучей оговорок)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Алгоритмы работают с итераторами!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Теперь мы готовы осознать, что итератор - не про итерирование.\n",
    "\n",
    "Итератор для алгоритмов требует реализацию методов, но КАК они будут реализованы - вопрос.\n",
    "\n",
    "\n",
    "```c++\n",
    "template<typename T>\n",
    "class MyIterator {\n",
    "    T& operator *() const {\n",
    "        // какая-то реализация\n",
    "    }\n",
    "    \n",
    "    void operator++() const {\n",
    "        // какая-то реализация, возможно, пустая\n",
    "    }\n",
    "    \n",
    "    ...    \n",
    "    \n",
    "};\n",
    "```\n",
    "\n",
    "Примеры:\n",
    "* `std::ostream_iterator<int>(std::cout, \" \")` - ~итератор, который выводит записываемое значение в `std::cout` через пробел\n",
    "* `std::back_inserter(v)` - ~итератор, который делает `push_back` записываемых значений в вектор `v`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример**: разные варианты сортировки через один алгоритм"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// отсортируем вектор по возрастанию\n",
    "void mysort_ascending(std::vector<int>& v)\n",
    "{\n",
    "    std::sort(v.begin(), v.end());\n",
    "}\n",
    "\n",
    "// отсортируем вектор по убыванию\n",
    "void mysort_descending(std::vector<int>& v)\n",
    "{\n",
    "    std::sort(v.rbegin(), v.rend());\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример**: вывод на консоль через алгоритм (подробно объяснить пример)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// copy - копирует последовательность\n",
    "//        https://en.cppreference.com/w/cpp/algorithm/copy\n",
    "void copy_example()\n",
    "{\n",
    "    std::vector<int> v = {1, 2, 3};\n",
    "    std::list<int> l = {4, 5, 6};\n",
    "    \n",
    "    std::copy(v.begin(), v.end(), l.begin());\n",
    "}\n",
    "\n",
    "// copy - копирует последовательность в OutputIt,\n",
    "//        но ведь можно и подшаманить OutputIt\n",
    "void print_sequence()\n",
    "{\n",
    "    std::vector<int> v = {1, 2, 3, 4, 5};\n",
    "    \n",
    "    std::copy(v.begin(), v.end(),\n",
    "              std::ostream_iterator<int>(std::cout, \" \"));\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример**: чтение (подробно объяснить пример)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<int> read_ints()\n",
    "{\n",
    "    return std::vector<int>{\n",
    "        std::istream_iterator<int>(std::cin),\n",
    "        std::istream_iterator<int>()       \n",
    "    };\n",
    "}\n",
    "\n",
    "int sum_ints()\n",
    "{\n",
    "    std::istringstream iss(\"1 2 3 4 5\");\n",
    "    \n",
    "    return std::reduce(\n",
    "        std::istream_iterator<int>(iss),\n",
    "        std::istream_iterator<int>());\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "И в то же время гибкости класса итераторов не хватает, чтобы простые конструкции реализовывались без лишних раздумий:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void copy_example_bug()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5};\n",
    "    std::vector<int> b;\n",
    "\n",
    "    std::copy(a.begin(), a.end(), b.begin());\n",
    "}\n",
    "\n",
    "void copy_example_fix1()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5};\n",
    "    std::vector<int> b;\n",
    "\n",
    "    b.resize(a.size(), 0);\n",
    "    std::copy(a.begin(), a.end(), b.begin());\n",
    "}\n",
    "\n",
    "void copy_example_fix2()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5};\n",
    "    std::vector<int> b;\n",
    "\n",
    "    std::copy(a.begin(), a.end(), std::back_inserter(b));\n",
    "    // back_inserter - специальный итератор, который в operator = вызывает b.push_back(...)\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void replace_copy_bug()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    std::vector<int> b;\n",
    "\n",
    "    std::replace_copy(a.begin(), a.end(), b.begin(), 2, 7);\n",
    "}\n",
    "\n",
    "void replace_copy_fix()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    std::vector<int> b;\n",
    "\n",
    "    std::replace_copy(a.begin(), a.end(), std::back_inserter(b), 2, 7);\n",
    "}\n",
    "\n",
    "void replace_copy_better()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    std::vector<int> b;\n",
    "\n",
    "    b.reserve(a.size());\n",
    "    std::replace_copy(a.begin(), a.end(), std::back_inserter(b), 2, 7);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### `std::remove` и `std::unique` - где чаще всего ошибаются"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void remove_usage_bug()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    std::remove(a.begin(), a.end(), 2);\n",
    "}\n",
    "\n",
    "void remove_usage_fix()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    auto new_end = std::remove(a.begin(), a.end(), 2);\n",
    "    a.resize(std::distance(a.begin(), new_end));\n",
    "}\n",
    "\n",
    "void remove_usage_fix_another_option()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    a.erase(std::remove(a.begin(), a.end(), 2),\n",
    "            a.end());\n",
    "}\n",
    "\n",
    "void remove_usage_list()\n",
    "{\n",
    "    std::list<int> l = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    l.remove(2); // list is an exception!\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void unique_usage_bug()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    std::sort(a.begin(), a.end());  // unique removes only adjacent uniques\n",
    "    std::unique(a.begin(), a.end());\n",
    "}\n",
    "\n",
    "void unique_usage_fix()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    std::sort(a.begin(), a.end()); // unique removes only adjacent uniques\n",
    "    auto new_end = std::unique(a.begin(), a.end());\n",
    "    a.resize(std::distance(a.begin(), new_end));\n",
    "}\n",
    "\n",
    "void unique_usage_list()\n",
    "{\n",
    "    std::list<int> l = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    l.sort();  // unique removes only adjacent uniques\n",
    "    l.unique();\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Обратить внимание на состояние контейнера после вызова remove:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void remove_result_content()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    auto new_end = std::remove(a.begin(), a.end(), 2);\n",
    "    \n",
    "    for (int x : a)\n",
    "        std::cout << x << \" \"; // ???\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "######  `std::erase` (C++ 20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/container/vector/erase2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для проблемы вызова `std::remove` по контейнерам решили написать shortcut для `std::vector`:\n",
    "\n",
    "(закинуть на godbolt на последний gcc, не забыть `-std=c++20`)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <algorithm>\n",
    "#include <iostream>\n",
    "#include <iterator>\n",
    "#include <string>\n",
    "#include <vector>\n",
    "\n",
    "int main() {\n",
    "    std::vector<std::string> container = {\n",
    "        \"Carthago\", \"Rome\", \"Rome\",\n",
    "        \"Carthago\", \"Paris\", \"Ciaro\",\n",
    "        \"Konstantinie\"};\n",
    "    std::erase(container, \"Carthago\");\n",
    "\n",
    "    std::copy(\n",
    "        container.begin(),\n",
    "        container.end(),\n",
    "        std::ostream_iterator<std::string>(std::cout, \" \"));\n",
    "    return 0;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вывод ожидаем:\n",
    "    \n",
    "```\n",
    "Rome Rome Paris Ciaro Konstantinie\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Но если так (см. на godbolt):\n",
    "\n",
    "```c++\n",
    "    ...\n",
    "    std::vector<std::string> container = {\n",
    "        \"Carthago\", \"Rome\", \"Rome\",\n",
    "        \"Carthago\", \"Paris\", \"Ciaro\",\n",
    "        \"Konstantinie\"};\n",
    "    std::erase(container, container.front());\n",
    "    ...\n",
    "```\n",
    "\n",
    "то вывод будет другим:\n",
    "\n",
    "```\n",
    "Rome Carthago Paris Ciaro Konstantinie\n",
    "```\n",
    "\n",
    "**Вопрос**: почему?\n",
    "\n",
    "<details>\n",
    "<summary>Ответ</summary>\n",
    "\n",
    "<p>\n",
    "    std::erase - шаблонный алгоритм. Он сравнивает по ссылке на первый элемент. std::erase модифицирует контейнер, вместе с ним модифицируя и первый элемент. Т.е. элемент для удаления изменяется неявно в процессе алгоритма.\n",
    "</p>\n",
    "</details>\n",
    "\n",
    "\n",
    "**Вопрос**: как починить?\n",
    "\n",
    "<details>\n",
    "<summary>Ответ</summary>\n",
    "\n",
    "<p>\n",
    "    сделать копию первого элемента и сравнивать с ней :(\n",
    "    \n",
    "    std::erase(container, std::string(container.front()));    \n",
    "    или    \n",
    "    std::erase(container, auto{container.front()});  // since C++23\n",
    "</p>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Лямбды - использование"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`find` по условию через функцию:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "bool is_underage(const Person& p) {\n",
    "    return p.age < 18;\n",
    "}\n",
    "\n",
    "std::vector<Person> people = { ... };\n",
    "\n",
    "auto it = std::find_if(\n",
    "    people.begin(),\n",
    "    people.end(),\n",
    "    is_underage);\n",
    "\n",
    "if (it != people.end())\n",
    "    std::cout << it->age << std::endl;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`find` по условию через лямбду:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<Person> people = { ... };\n",
    "\n",
    "auto it = std::find_if(\n",
    "    people.begin(),\n",
    "    people.end(),\n",
    "    [](const Person& p){ return p.age < 18; });\n",
    "    \n",
    "if (it != people.end())\n",
    "    std::cout << it->age << std::endl;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`count_if` - подсчёт числа элементов"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<Person> people = { ... };\n",
    "        \n",
    "const int underage_count = std::count_if(people.begin(), people.end(),\n",
    "                                         [](const Person& p){ return p.age < 18; });\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`all_of`, `any_of`, `none_of`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "auto is_underage = [](const Person& p){ return p.age < 18; };\n",
    "\n",
    "bool all_young = std::all_of(people.begin(), people.end(), is_underage);\n",
    "bool any_young = std::any_of(people.begin(), people.end(), is_underage);\n",
    "bool all_old   = std::none_of(people.begin(), people.end(), is_underage);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`transform`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void toupper_inplace(std::string& s)\n",
    "{\n",
    "    std::transform(\n",
    "        s.begin(), s.end(),  // input range\n",
    "        s.begin(),           // output\n",
    "        [](unsigned char c) -> unsigned char { return std::toupper(c); });  // function\n",
    "}\n",
    "\n",
    "void print_toupper(std::string& s)\n",
    "{\n",
    "    std::tranform(\n",
    "        ...  // Упражнение\n",
    "    );\n",
    "}\n",
    "\n",
    "// map-reduce example\n",
    "int sum_of_squarries(const std::vector<int>& v)\n",
    "{\n",
    "    return std::transform_reduce(\n",
    "        v.begin(), v.end(),                     // последовательность\n",
    "        0,                                      // начальный элемент в reduce-шаге (как в accumulate)\n",
    "        [](int sum, int x) { return sum + x; }, // операция reduce\n",
    "        [](int x){ return x * x; });            // операция transform\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "binary search:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<int> v = { 1, 1, 2, 3, 4, 4, 4, 5, 5, 6 };\n",
    "        \n",
    "auto lower = std::lower_bound(v.begin(), v.end(), 4);\n",
    "auto upper = std::upper_bound(v.begin(), v.end(), 4);\n",
    "        \n",
    "std::copy(lower, upper,\n",
    "          std::ostream_iterator<int>(std::cout, \" \"));\n",
    "// output: 4 4 4\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "if (std::binary_search(v.begin(), v.end(), 5))\n",
    "    std::cout << \"found\";\n",
    "else\n",
    "    std::cout << \"not found\";\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`set` operations:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Замечание**: специфика set operations, что они работают только с отсортированными последовательностями"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<int> v1 = {...};\n",
    "std::sort(v1.begin(), v1.end());\n",
    "        \n",
    "std::vector<int> v2 = {...};\n",
    "std::sort(v2.begin(), v2.end());\n",
    "\n",
    "// check for subset:\n",
    "if (std::includes(v1.begin(), v1.end(),\n",
    "                  v2.begin(), v2.end())) {\n",
    "    std::cout << \"v2 is subset of v1\";\n",
    "}\n",
    "\n",
    "// build union\n",
    "std::vector<int> v3 = {...};\n",
    "std::set_union(v1.begin(), v1.end(),  // отсортированная последовательность 1\n",
    "               v2.begin(), v2.end(),  // отсортированная последовательность 2\n",
    "               std::back_inserter(v3));  // куда складывать результат\n",
    "// что здесь можно было бы добавить?\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`min`/`max`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<int> v = { ... };\n",
    "\n",
    "auto it_min = std::min_element(v.begin(), v.end());\n",
    "auto it_max = std::max_element(v.begin(), v.end());\n",
    "// почему возвращается итератор, а не сразу ссылка на минимальный элемент?\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<Person> people = { ... };\n",
    "        \n",
    "auto it_min = std::min_element(people.begin(), people.end(),\n",
    "                               [](const Person& l, const Person& r) {\n",
    "                                   return l.name < r.name;\n",
    "                               });  // поиск первого по алфавиту\n",
    "\n",
    "auto it_max = std::max_element(people.begin(), people.end(),\n",
    "                               [](const Person& l, const Person& r) {\n",
    "                                   return l.age < r.age;\n",
    "                               });  // поиск самого старшего\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "etc. etc. etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Execution policies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "С С++17 можно запускать некоторые алгоритмы в параллельное исполнение одним дополнительным аргументом:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::reduce(std::execution::par, v.begin(), v.end());\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* `std::execution::seq`\n",
    "    - последовательно на одном потоке\n",
    "    - порядок обработки элементов соответствует их порядку в последовательности\n",
    "* `std::execution::par`\n",
    "    - STL вправе (но не обязана) выполнить алгоритм параллельно на нескольких потоках\n",
    "    - порядок обработки элементов на одном потоке соответствует их порядку в последовательности\n",
    "* `std::execution::unseq`\n",
    "    - последовательно на одном потоке\n",
    "    - порядок обработки элементов может не соответствовать их порядку в последовательности (например, рарешается применять векторизацию)\n",
    "* `std::execution::par_unseq`\n",
    "    - STL вправе (но не обязана) выполнить алгоритм параллельно на нескольких потоках\n",
    "    - порядок обработки элементов произвольный"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Заметки про производительность ради которой всё это затевалось:\n",
    "https://www.bfilipek.com/2018/11/parallel-alg-perf.html\n",
    "\n",
    "Спойлер: не всё так однозначно"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "За рамками рассказа:\n",
    "* boost algorithms\n",
    "* bit manipulations\n",
    "* math operations\n",
    "* другие реализации алгоритмов (EASTL)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Лямбды - детали"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Откуда ноги растут - из функторов"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Во времена до С++11:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "bool is_underage(const Person& person)\n",
    "{\n",
    "    return person.age < 18;\n",
    "}\n",
    "\n",
    "std::vector<Person> people = { ... };\n",
    "\n",
    "auto it = std::find_if(people.begin(), people.end(), is_underage);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Либо через функтор:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "struct IsUnderageChecker\n",
    "{\n",
    "    bool operator()(const Person& person) const\n",
    "    {\n",
    "        return person.age < 18;\n",
    "    }    \n",
    "};\n",
    "\n",
    "std::vector<Person> people = { ... };\n",
    "        \n",
    "auto it = std::find_if(people.begin(), people.end(), IsUnderageChecker());\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Функтор - класс с определённым `operator()`. Объекты такого класса можно \"вызывать\":\n",
    "\n",
    "**Пример**:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "Person ilya{\"Ilya Muromec\", 32};\n",
    "\n",
    "IsUnderageChecker is_underage_checker;\n",
    "\n",
    "if (is_underage_checker(ilya))\n",
    "    std::cout << \"Ilya is old\";\n",
    "else\n",
    "    std::cout << \"Ilya is young\";\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Конкретно для этого примера (с некоторыми оговорками) не важно, свободная функция `is_underage` или функтор `IsUnderageChecker`, но иногда может понадобится и класс.\n",
    "\n",
    "**Упражение**: Приведите пример. Подсказка: в чём большое отличиие функции от класса?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Вариант**:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "class АgeLessChecker {\n",
    "public:\n",
    "    explicit АgeLessChecker(int bound) : bound_(bound) {}\n",
    "    \n",
    "    bool operator()(const Person& person) const {\n",
    "        return person.age < bound_;\n",
    "    }\n",
    "    \n",
    "private:\n",
    "    int bound_;\n",
    "};\n",
    "\n",
    "\n",
    "Person ilya{\"Ilya Muromec\", 32};\n",
    "\n",
    "АgeLessChecker ilya_maturity_checker{33};\n",
    "\n",
    "if (ilya_maturity_checker(ilya))\n",
    "    std::cout << \"time to fight!\";\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Вариант**:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "class NameInSetChecker {\n",
    "public:\n",
    "    explicit NameInSetChecker(std::set<std::string> allowed_names)\n",
    "        : allowed_names_(std::move(allowed_names))\n",
    "    {}\n",
    "    \n",
    "    bool operator()(const Person& person) const {\n",
    "        return allowed_names_.count(person.name) > 0;\n",
    "    }\n",
    "    \n",
    "private:\n",
    "    std::set<std::string> allowed_names_;\n",
    "};\n",
    "\n",
    "std::vector<Person> people = { ... };\n",
    "\n",
    "const std::set<std::string> allowed_names{\"Balin\", \"Dvalin\", \"Gloin\"};\n",
    "\n",
    "auto it = std::find_if(people.begin(), people.end(),\n",
    "                       NameInSetChecker(allowed_names));\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Более интересный пример**:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "struct HTMLPrinter\n",
    "{\n",
    "    void operator()(int x) const { std::cout << \"<p> int value = \" << x << \" </p>\"; }\n",
    "    void operator()(double x) const { std::cout << \"<p> dlb value = \" << x << \" </p>\"; }\n",
    "};\n",
    "\n",
    "HTMLPrinter printer;\n",
    "printer(5);    // <p> int value = 5 </p>\n",
    "printer(5.0);  // <p> dbl value = 5.000000 </p>\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[Правила работы с функторами](https://cpp.com.ru/meyers/ch6.html). Основное:\n",
    "* Классы функторов для алгоритмов передаются по значению, а значит их следует проектировать копируемыми\n",
    "* Желательно, чтобы функторы для алгоритмов не изменяли своё состояние (нет гарантий, что функтор не будет раскопирован))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Функторы - гибкий и богатый инструмент, за исключением того, что требуют большого объёма кода для реализации. Лямбду можно рассматривать как сокращённую запись функтора, который компилятор сгенерирует неявно.*\n",
    "\n",
    "(утверждение может быть поднатянуто с точки зрения оптимизаций, применяемых компилятором к лямбдам и функторам, но для понимания лямбд вполне подойдёт)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Контекст, захват и передача параметров. Dangling references, правила"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Лямбда без состояния:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "auto it = std::find_if(people.begin(), people.end(),\n",
    "                       [](const Person& p){ return p.age < 18; });\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Когда нужно запомнить состояние (сделать поле данных у функтора):"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "auto find_first_younger(const std::vector<Person>& people, int age)\n",
    "{\n",
    "    return std::find_if(people.begin(), people.end(),\n",
    "                        [](const Person& p){ return p.age < age; });    \n",
    "}\n",
    "\n",
    "// Не скомпилируется, т.к. компилятор не знает, каким образом\n",
    "// хранить age в лямбде. Ему нужно это явно указать.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Захватывать данные в лямбду можно двумя способами:\n",
    "1. с копированием значения\n",
    "    * можно представлять как отдельное поле типа `T` в функторе\n",
    "2. по ссылке\n",
    "    * можно представлять  как отдельное поле типа `T*` или `T&` в функторе"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "int age = 33;\n",
    "auto too_young = [age](const Person& p){ return p.age < age; }; \n",
    "age = 18;\n",
    "// age будет скопирован по значению\n",
    "// в поиске используется значение 33\n",
    "\n",
    "std::find_if(people.begin(), people.end(), too_young);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "int age = 33;\n",
    "auto too_young = [&age](const Person& p){ return p.age < age; }; \n",
    "age = 18;\n",
    "// age будет использован по ссылке\n",
    "// в поиске используется значение 18\n",
    "\n",
    "std::find_if(people.begin(), people.end(), too_young);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Можно указывать способ захвата \"по умолчанию\". Тогда все внешние объекты, упоминаемые внутри лямбды, будут захвачены соответственно:\n",
    "\n",
    "* всё захватывать по значению:\n",
    "\n",
    "```c++\n",
    "int age = 33;\n",
    "auto too_young = [=](const Person& p){ return p.age < age; };\n",
    "```\n",
    "\n",
    "* всё захватывать по ссылке:\n",
    "\n",
    "```c++\n",
    "int age = 33;\n",
    "auto too_young = [&](const Person& p){ return p.age < age; };\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Примеры:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// объект int очень дешёв для копирования,\n",
    "// а разыменовывать по ссылке его дольше,\n",
    "// поэтому захватим по значению\n",
    "\n",
    "int age = read_age_limit();\n",
    "\n",
    "auto it = std::find_if(people.begin(), people.end(),\n",
    "                       [age](const Person& p) { return p.age < age; });\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// объект std::set<std::string> очень дорогой для копирования,\n",
    "// лучше потратить немножко на дополнительные jump-ы по ссылкам,\n",
    "// поэтому захватим по ссылке\n",
    "\n",
    "std::set<std::string> allowed_names = ...;\n",
    "                \n",
    "auto it = std::find_if(people.begin(), people.end(),\n",
    "                       [&allowed_names](const Person& p) { return allowed_names.count(p.name) > 0; });\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Упражнение:** что здесь происходит?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::set<std::string> allowed_names = ...;\n",
    "std::set<std::string>* p_allowed_names = &allowed_names;\n",
    "                \n",
    "auto it = std::find_if(people.begin(), people.end(),\n",
    "                       [p_allowed_names](const Person& p) { return p_allowed_names->count(p.name) > 0; });\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Dangling references problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "auto make_names_checker()\n",
    "{\n",
    "    std::set<std::string> allowed_names = ...;                \n",
    "    return [&allowed_names](const Person& p) { return allowed_names.count(p.name) > 0; };\n",
    "}\n",
    "\n",
    "auto names_checker = make_names_checker();\n",
    "names_checker(Person(\"Ilya\"));  // ooooops\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* какая здесь проблема?\n",
    "* как с ней бороться?\n",
    "* правила?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Возвращаемый тип"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Компилятор автоматически выводит возвращаемый тип, опираясь на тип выражения в `return`. Но можно и указать тип явно:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "auto too_young = [](const Person& p) { return p.age < 18; };\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "auto too_young = [](const Person& p) -> bool { return p.age < 18; }\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Упражнение**: в каких случаях это необходимо?\n",
    "\n",
    "Ответ-пример:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// без явного указания типа возвращемого значения код не скопилируется\n",
    "auto build_full_name = [](const Person& p) -> std::string {\n",
    "\n",
    "    // return type is const char *\n",
    "    if (p.name.empty() && p.surname.empty())\n",
    "        return \"unknown\";\n",
    "\n",
    "    // return type is std::string\n",
    "    return p.name + \" \" + p.surname;\n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// без явного указания типа возвращемого значения код не скопилируется\n",
    "auto find_lowest_point = [](const std::vector<Point>& points) -> std::optional<Point> {\n",
    " \n",
    "    // return type is std::nullopt_t\n",
    "    if (points.empty())\n",
    "        return std::nullopt;\n",
    "    \n",
    "    // return type is Point\n",
    "    return *std::min_element(points.begin(), points.end(),\n",
    "                             [](const Point l, const Point r) { return l.z < r.z; });\n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### mutable - лямбды"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Использование ключевого слова `mutable` означает, что данные, захваченные копированием значения, лямбда вправе поменять:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void mutable_lambda_example()\n",
    "{\n",
    "    auto fun = [i = 0]() mutable -> bool {\n",
    "        ++i;\n",
    "        return i != 4;\n",
    "    };\n",
    "    while (fun())\n",
    "        std::cout << \"ho\";  // напечатает hohoho\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### immediately call labmdas"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Рассмотрим пример:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void process_log_file(const std::string& basename)\n",
    "{\n",
    "    const std::string filepath = basename + \".log\";\n",
    "    std::ifstream ifs(filepath);\n",
    "    if (!ifs)\n",
    "        throw std::runtime_error(\"filed to open log file on read\");\n",
    "\n",
    "    std::vector<Record> log_records{std::istreambuf_iterator<Record>(ifs),\n",
    "                                    std::istreambuf_iterator<Record>()};\n",
    "    std::reverse(log_records.begin(), log_records.end());\n",
    "    \n",
    "    \n",
    "    ... 200+ lines of records processing further\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Проблемы такой реализации:\n",
    "* скорее всего `filepath` и `ifs` больше не нужны, но:\n",
    "    - переменные видны в коде ниже и надо разбираться, нужны они там или нет\n",
    "    - переменные держат за собой память и открытый дескриптор файла, а эти ресурсы уже можно и освободить\n",
    "* формирование `log_records` завершено и далее меняться не будет. Его бы как-нибудь пометить `const`, но язык такое не позволяет."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Возможные решения: выделить функцию `read_log_records` или завернуть в immediately call lambda:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void process_log_file(const std::string& basename)\n",
    "{\n",
    "    const std::vector<Record> log_records = [&basename](){\n",
    "        const std::string filepath = basename + \".log\";\n",
    "        std::ifstream ifs(filepath);\n",
    "        if (!ifs)\n",
    "            throw std::runtime_error(\"filed to open log file on read\");\n",
    "\n",
    "        std::vector<Record> log_records{std::istreambuf_iterator<Record>(ifs),\n",
    "                                        std::istreambuf_iterator<Record>()};\n",
    "        std::reverse(log_records.begin(), log_records.end());\n",
    "        return log_records;\n",
    "    }();\n",
    "    \n",
    "    ... 200+ lines of records processing further\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Не стоит бояться оверхеда в релизе на вызов immediately call - лямбд. Компиляторы хороши в их оптимизации:\n",
    "\n",
    "(закинуть код на godbolt.org)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// оптимизация для compile-time вычислений\n",
    "int get_5() noexcept {\n",
    "    return [](){ return 5; }();    \n",
    "}\n",
    "\n",
    "// оптимизация для чуть более сложных функций\n",
    "double f_1(const double x, const double y) noexcept {\n",
    "    const double l = x*x +  y*y;\n",
    "    return x / l + y / l;\n",
    "}\n",
    "\n",
    "double f_2(const double x, const double y) noexcept {\n",
    "    const double add1 = [=](){\n",
    "        const double l = x*x + y*y;\n",
    "        return x / l;\n",
    "    }();\n",
    "    const double add2 = [=](){\n",
    "        const double l = x*x + y*y;\n",
    "        return y / l;\n",
    "    }();\n",
    "    return add1 + add2;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Конечно, пример не есть доказательство, но, тем не менее, и gcc, и clang смогли сгенерировать одинаковый код для `f_1` и `f_2`, несмотря на наличие лишних вызовов и доп. вычислений в `f_2`.\n",
    "\n",
    "На уровне оптимизаций для отладки `-O0` компилятор не может себе позволить инлайнить immediately call лямбды, там код отличается, это нормально.\n",
    "\n",
    "Поэтому, если performance для `-O0` важен (бывают такие проекты), то в горячих функциях (коих **очень мало**) лучше воздержаться от immediately call."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### generic lambda"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ничто не мешает сделать `operator()` шаблонным:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "struct HTMLPrinter\n",
    "{\n",
    "    template<typename T>\n",
    "    void operator()(const T& x) const { std::cout << \"<p> value = \" << x << \" </p>\"; }\n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Аналогично можно поступить и для лямбды, заменив тип аргумента словом `auto`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "auto too_young = [](const auto& p) { return p.age < 18; };\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "generic lambda как и template-метод позволяют вызывать для разных аргументов"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "bool f()\n",
    "{\n",
    "    auto less = [](const auto& x, const auto& y) { return x < y; };\n",
    "    return less(3, 5) && less(3.0, 5.0);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пару слов об использовании и цене"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### `noexcept` lambda"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`noexcept` имеет аналогичную семантику как и `noexcept` для обычных функций."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "auto too_young = [](const auto& p) noexcept { return p.age < 18; };\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Сохранение лямбда-функции как объекта."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Проблема в записи лямбды в поле класса заключается в том, что тип лямбда-функции создаётся в момент генерации лямбды. Его нельзя выписать явно (иногда можно неявно)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Варианты решения проблемы:\n",
    "1. Использовать шаблоны\n",
    "2. Заворачивать лямбды в `std::function`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "class ImagesManager {\n",
    "public:\n",
    "    ImagesManager(std::function<Image(int)> img_searcher)\n",
    "        : img_searcher_(std::move(img_searcher))\n",
    "    {}\n",
    "    \n",
    "    ...    \n",
    "private:\n",
    "    std::function<Image(int, int)> img_searcher_;\n",
    "};\n",
    "\n",
    "// client code:\n",
    "auto search_image = [](const int key) -> Image { ... };\n",
    "ImagesManager manager(search_image);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "template<typename ImgSearcherT>\n",
    "class ImagesManager {\n",
    "public:\n",
    "    ImagesManager() {}\n",
    "    \n",
    "    ...    \n",
    "private:\n",
    "    ImgSearcherT img_searcher_;\n",
    "};\n",
    "\n",
    "\n",
    "// объяснить, почему это вообще работает\n",
    "// client code:\n",
    "auto search_image = [](const int key) -> Image { ... };\n",
    "ImagesManager<decltype(search_image)> manager;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Упражнение**: каковы плюсы и минусы обоих из вариантов?"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
